package backtrace;

import java.util.*;

public class leetcode51N皇后 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] queue = new int[n];
        Set<Integer> column = new HashSet<>();
        Set<Integer> left = new HashSet<>();
        Set<Integer> right = new HashSet<>();
        dfs(result, queue, n, 0, column, left, right);
        return result;
    }

    public void dfs(List<List<String>> result, int[] queue, int n, int level, Set<Integer> column, Set<Integer> left, Set<Integer> right) {
        if (level == n) {
            result.add(generateList(queue));
        } else {
            for (int i = 0; i < n; i++) {
                if (column.contains(i)) {
                    continue;
                }
                int leftRel = i + level;
                if (left.contains(leftRel)) {
                    continue;
                }
                int rightRel = i - level;
                if (right.contains(rightRel)) {
                    continue;
                }
                queue[level] = i;
                column.add(i);
                left.add(leftRel);
                right.add(rightRel);
                dfs(result, queue, n, level + 1, column, left, right);
                column.remove(i);
                left.remove(leftRel);
                right.remove(rightRel);
            }
        }
    }

    public List<String> generateList(int[] queue) {
        int length = queue.length;
        List<String> result = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            char[] row = new char[length];
            Arrays.fill(row,'.');
            row[queue[i]] = 'Q';
            String rowStr = new String(row);
            result.add(rowStr);
        }
        return result;
    }
}
